﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Collections.Concurrent;

namespace IOP.Models.Queue
{
    /// <summary>
    /// 索引优先队列
    /// </summary>
    /// <typeparam name="TKey"></typeparam>
    /// <typeparam name="TValue">存储的值</typeparam>
    public class IndexPriorityQueue<TKey, TValue>
        where TKey : IComparable<TKey>
    {
        /// <summary>
        /// 默认容量
        /// </summary>
        public const int DefaultCapacity = 128;
        /// <summary>
        /// 数量
        /// </summary>
        public int Count => Volatile.Read(ref _N);
        /// <summary>
        /// 是否为空
        /// </summary>
        public bool IsEmpty => Volatile.Read(ref _N) == 0;
        /// <summary>
        /// 索引数组
        /// </summary>
        private TKey[] _PQ;
        /// <summary>
        /// 存储具体数据的字典
        /// </summary>
        private readonly ConcurrentDictionary<TKey, TValue> _Elements;
        /// <summary>
        /// 当前索引数组所使用的最大下标
        /// </summary>
        private int _N = 0;
        /// <summary>
        /// 当前队列容量
        /// </summary>
        private int _Capacity;
        /// <summary>
        /// 排序模型
        /// </summary>
        private SequenceMode _Mode;

        /// <summary>
        /// 自旋锁
        /// </summary>
        private SpinLock _SyncRoot = new SpinLock();

        /// <summary>
        /// 互斥锁
        /// </summary>
        private readonly object _Monitor = new object();

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="sequenceMode"></param>
        public IndexPriorityQueue(SequenceMode sequenceMode = SequenceMode.MAX)
        {
            int c = DefaultCapacity + 1;
            _PQ = new TKey[DefaultCapacity + 1];
            _Capacity = c;
            _Elements = new ConcurrentDictionary<TKey, TValue>();
            _Mode = sequenceMode;
        }
        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="capacity"></param>
        /// <param name="sequenceMode"></param>
        public IndexPriorityQueue(int capacity, SequenceMode sequenceMode = SequenceMode.MAX)
        {
            int c = capacity + 1;
            _PQ = new TKey[c];
            _Capacity = c;
            _Elements = new ConcurrentDictionary<TKey, TValue>();
            _Mode = sequenceMode;
        }

        /// <summary>
        /// 尝试入队列
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public bool TryEnqueue(TKey key, TValue value)
        {
            if (_Elements.ContainsKey(key)) return false;
            AddElemet(key, value);
            return true;
        }
        /// <summary>
        /// 入队列
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public void Enqueue(TKey key, TValue value)
        {
            if (_Elements.ContainsKey(key)) throw new ArgumentException($"The Dictionary has already has the same key , the key is {key.ToString()}");
            AddElemet(key, value);
        }
        /// <summary>
        /// 添加元素
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void AddElemet(TKey key, TValue value)
        {
            bool getLock = false;
            try
            {
                int n = Interlocked.Increment(ref _N);
                if (n >= _Capacity) Dilatation(_Capacity * 2);
                _SyncRoot.Enter(ref getLock);
                _PQ[n] = key;
                Swim(n);
            }
            finally
            {
                if (getLock) _SyncRoot.Exit();
            }
            _Elements.AddOrUpdate(key, value, (newKey, newValue) => newValue);
        }

        /// <summary>
        /// 扩容
        /// </summary>
        /// <param name="size"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Dilatation(int size)
        {
            if (size < _Capacity) return;
            Volatile.Write(ref _Capacity, size);
            lock (_Monitor)
            {
                var newArray = new TKey[size];
                _PQ.CopyTo(newArray, 0);
                _PQ = newArray;
            }
        }

        /// <summary>
        /// 从索引拿出最大(小)Key值所对应的元素
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool TryDequeue(out TValue value)
        {
            TKey first;
            bool getLock = false;
            value = default;
            if (IsEmpty) return false;
            int n = Interlocked.Decrement(ref _N);
            try
            {
                _SyncRoot.Enter(ref getLock);
                first = _PQ[1];
                Exch(1, n+1);
                _PQ[n+1] = default;
                Sink(1, n);
            }
            finally
            {
                if (getLock) _SyncRoot.Exit();
            }
            bool t = _Elements.TryRemove(first, out value);
            if (!t)
            {
                throw new Exception("???");
            }
            return t;
        }
        /// <summary>
        /// 从索引拿出最大(小)Key值所对应的元素
        /// </summary>
        /// <returns></returns>
        public TValue Dequeue()
        {
            if (IsEmpty) throw new NullReferenceException("The queue is empty");
            TryDequeue(out TValue value);
            return value;
        }
        /// <summary>
        /// 获取最大(小)Key值
        /// </summary>
        /// <returns></returns>
        public TKey GetFirstKey()
        {
            return _PQ[1];
        }
        /// <summary>
        /// 变更优先队列中指定下标的值
        /// </summary>
        /// <param name="index"></param>
        /// <param name="value"></param>
        public void Change(int index, TValue value)
        {
            int n = Volatile.Read(ref _N);
            if (index > n) throw new IndexOutOfRangeException($"The Target Index {index} is out of queue count {_N}");
            TKey key = _PQ[index];
            if (_Elements.ContainsKey(key)) _Elements[key] = value;
        }

        /// <summary>
        /// 获取值
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public void TryGetValue(TKey key, out TValue value)
        {
            _Elements.TryGetValue(key, out value);
        }

        /// <summary>
        /// 上浮
        /// </summary>
        /// <param name="index"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Swim(int index)
        {
            switch (_Mode)
            {
                case SequenceMode.MAX:
                    while (index > 1 && Less(index / 2, index))
                    {
                        Exch(index / 2, index);
                        index /= 2;
                    }
                    break;
                case SequenceMode.MIN:
                    while (index > 1 && Big(index / 2, index))
                    {
                        Exch(index / 2, index);
                        index /= 2;
                    }
                    break;
            }
        }
        /// <summary>
        /// 下沉
        /// </summary>
        /// <param name="index"></param>
        /// <param name="n"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Sink(int index, int n)
        {
            switch (_Mode)
            {
                case SequenceMode.MAX:
                    while (2 * index <= n)
                    {
                        int j = 2 * index;
                        if (j < n && Less(j, j + 1)) j++;
                        if (!Less(index, j)) break;
                        Exch(index, j);
                        index = j;
                    }
                    break;
                case SequenceMode.MIN:
                    while (2 * index <= n)
                    {
                        int j = 2 * index;
                        if (j < n && Big(j, j + 1)) j++;
                        if (!Big(index, j)) break;
                        Exch(index, j);
                        index = j;
                    }
                    break;
            }
        }
        /// <summary>
        /// 比较索引数组的两个Key值哪个较小
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        private bool Less(int i, int j)
        {
            return _PQ[i].CompareTo(_PQ[j]) < 0;
        }
        /// <summary>
        /// 比较索引数组的两个Key值哪个较大
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        private bool Big(int i, int j)
        {
            return _PQ[i].CompareTo(_PQ[j]) > 0;
        }
        /// <summary>
        /// 交换位置
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        private void Exch(int i, int j)
        {
            TKey key = _PQ[i];
            _PQ[i] = _PQ[j];
            _PQ[j] = key;
        }
    }
}
